package com.dhu.graph.utils;

import java.util.Arrays;

/**
 * @ Author ：snow
 * @ Date   ：Created in 2020-05-08
 * @ Description：最小优先队列
 * @ Modified By：
 * @ Version:
 */
public class MinPQ<Key extends Comparable<Key>> {
    private Key pq[];
    private int count;
    private int capacity;

    private static final int DEFAULT_CAPACITY = 16;
    public MinPQ(){
        this.capacity = DEFAULT_CAPACITY;
        this.pq = (Key [])new Object[DEFAULT_CAPACITY];
    }
    public MinPQ(int capacity){
        this.capacity = capacity;
        pq = (Key[]) new Object[capacity];
    }

    public void insert(Key k){
        ensureCapacityInternal();
        pq[++count] = k;
        swim(count);
    }
    public Key deleteMin(){
        Key ret = pq[1];
        exchange(1, count);
        pq[count --] = null;
        ensureCapacityInternal();
        return ret;
    }
    public boolean isEmpty(){
        return count == 0;
    }
    private void resize(int newCap){
        Key[] newPq = Arrays.copyOf(pq, newCap);
        pq = newPq;
        capacity = newCap;
    }
    /**
     * pq[i] 是否小于等于 pq[j]
     * @param i
     * @param j
     * @return
     */
    private boolean less(int i, int j){
        int cmp = pq[i].compareTo(pq[j]);
        return cmp < 0;
    }

    /**
     * 元素pq[i]上浮
     * @param i
     */
    private void swim(int i){
        while (i > 1 && less(i, i / 2)){
            exchange(i, i / 2);
        }
    }

    /**
     * 元素pq[i]下沉
     * @param i
     */
    private void sink(int i){
        while (2 * i <= count){
            int j = 2 * i;
            if (j < count && !less(j, j + 1) ) j++;
            if (less(i, j)) break;
            else
                exchange(i, j);
            i = j;
        }
    }
    private void exchange(int i, int j){
        Key temp = pq[i];
        pq[i] = pq[j];
        pq[j] = temp;
    }
    private void ensureCapacityInternal(){
        if (capacity - count < 2){
            resize(capacity * 2);
        }else if (capacity - count > capacity / 2){
            resize(capacity / 2);
        }
    }
}
